package SuanFa;
import java.util.*;
public class DongTai {
    public static void main(String[] args) {
        String s="babad";
//        Solution so=new Solution();
        int n=3;
        int[] prices={1,2,3,4,5};
        List<String> wordDict=new ArrayList<>();
        wordDict.add("leet");
        wordDict.add("code");
        int[] nums1={1,4,2};
        int[] nums2={1,2,4};
        int[] num={3,1,3,5,6};

//        so.moneyMin(num,16);
//        System.out.println(so.moneyMin(num,16));
//        so.isSubsequence("","asdasd");
//        so.maxUncrossedLines(nums1,nums2);
//        so.maxProfit(prices);
//        so.rob(prices);
//        so.numSquares(12);
//        so.lastStoneWeightII(prices);
//        so.climbStairs(3);
//        so.wordBreak("leetcode",wordDict);
//        so.partition("aab");
//        so.maxProfit(prices);
        //so.isInterleave("aabcc","dbbca","aadbbcbcac");
        //List f=so.generateParenthesis(n);
//        for ( int i=0;i< f.size();i++ ){
//            System.out.println(f.get(i));
//        }
        //Solution so=new Solution();
        //String s0=so.longestPalindrome(s);
        //System.out.print(s0);
    }

}

//class Solution{
//    public int moneyMin(int nums[],int hp){
//        int[] f=new int[hp+1];
//        f[0]=0;
//        int sum=0;
//        //找一个不可能达到的值
//        for ( int i=0;i<nums.length;i++ ){
//            sum+=nums[i];
//        }
//        for ( int i=1;i<hp+1;i++ ){
//            f[i]=sum+1;
//        }
////        for ( int i=0;i<nums.length;i++ ){
////            for ( int j=nums[i];j<hp+1;j++ ){
////                f[j]=Math.min(f[j],f[j-nums[i]]);
////            }
////        }
////        for ( int i=0;i<hp+1;i++ ){
////            for ( int j=0;j<nums.length;j++ ){
////                if ( i>=nums[j] ){
////                    f[i]=Math.min(f[i],f[i-nums[j]]+nums[j]);
////                }
////            }
////        }
//        for ( int i=0;i<nums.length;i++ ){
//            for ( int j=hp;j>=nums[i];j-- ){
//                f[j]=Math.min(f[j],f[j-nums[i]]+nums[i] );
//            }
//        }
//        if ( f[hp]!=sum+1){
//            return f[hp];
//        }else{
//            //进行遍历，每一个不是无法到达值的数进行加满足大于等于hp的条件然后取min
//        }
//
//    }
//}


//class Solution {
//    public boolean isSubsequence(String s, String t) {
//        String[] ss=s.split("");
//        String[] st=t.split("");
//        boolean[] f=new boolean[s.length()+1];
//        for ( int i=1;i<s.length()+1;i++ ){
//            f[i]=false;
//        }
//        f[0]=true;
//        int idx=0;
//        for ( int i=1;i<s.length()+1;i++ ){
//            for ( int j=idx;j<t.length();j++ ){
//                if ( ss[i-1].equals(st[j])&&f[i-1]==true ){
//                    f[i]=true;
//                    idx=++j;
//                }
//            }
//        }
//        return f[s.length()];
//    }
//}

//class Solution {
//    public int maxUncrossedLines(int[] nums1, int[] nums2) {
//        //可以将这题看成是两个字符串的公共子序列的最大值
////        String[] str1=nums1.toString().split("");//错了，不能这样转化
////        String[] str2=nums2.toString().split("");
//        int[][] f=new int[str1.length+1][str2.length+1];
//        int max=0;
//        for ( int i=1;i<=str1.length;i++ ){
//            for ( int j=1;j<=str2.length;j++ ){
//                if ( str1[i-1].equals(str2[j-1]) ){
//                    f[i][j]=f[i-1][j-1]+1;
//                    max=Math.max(max,f[i][j]);
//                }else{
//                    f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
//                    max=Math.max(max,f[i][j]);
//                }
//            }
//        }
//        return max;
//    }
//}

//class Solution {
//    public int longestCommonSubsequence(String text1, String text2) {
//        String str1[]=text1.split("");
//        String str2[]=text2.split("");
//        int[][] f=new int[str1.length+1][str2.length+1];
////        int max=0;
////        for ( int i=1;i<str1.length+1;i++ ){
////            for ( int j=1;j<str2.length+1;j++ ){
////                if ( str1[i-1].equals(str2[j-1]) ){
////                    max++;
////                }
////            }
////        }
////        return max;
//        for ( int i=1;i<str1.length;i++ ){
//            for ( int j=1;j<str2.length;j++ ){
//                if ( str1[i-1].equals(str2[j-1]) ){
//                    f[i][j]=f[i-1][j-1]+1;
//                }else{
//                    f[i][j]=Math.max(f[i-2][j-1],f[i-1][j-2]);
//                }
//            }
//        }
//        return f[str1.length+1][str2.length+1];
//    }
//}

//class Solution {
//    public int findLength(int[] nums1, int[] nums2) {
//        int[][] f=new int[nums1.length+1][nums2.length+1];
//        int max=0;
//        for ( int i=1;i<=nums1.length;i++ ){
//            for ( int j=1;j<=nums2.length;j++ ){
//                if ( nums1[i-1]==nums2[j-1] ){
//                    f[i][j]=f[i-1][j-1]+1;
//                }
//                max=Math.max(max,f[i][j]);
//            }
//        }
//        return max;
//
//    }
//}

//class Solution {
//    public int lengthOfLIS(int[] nums) {
//         int[] f=new int[nums.length];
//         int max=0;
//         f[0]=1;
//         for ( int i=1;i<nums.length;i++ ){
//             f[i]=1;
//             for ( int j=0;j<i;j++ ){
//                 if ( nums[i]>nums[j] ){
//                     f[i]=Math.max(f[i],f[j]+1);
//                 }
//                 if ( nums[i]==nums[j] ){
//                     f[i]=Math.max(f[i],f[j]);
//                 }
//             }
//             max=Math.max(max,f[i]);
//         }
//         return max;
//    }
//}

//class Solution {
//    public int maxProfit(int k, int[] prices) {
//        int num=2*k+1;
//        int[][] f=new int[prices.length][num];
//        //给f赋上初始状态
//        for ( int i=0;i<num;i++ ){
//            if ( i%2!=0 ){
//                f[0][i]=-prices[0];
//            }
//        }
//        //开始递推公式
//        for ( int i=1;i<prices.length;i++ ){
//            f[i][0]=0;
//            for ( int j=1;j<num;j++ ){
//                if ( j%2!=0 )
//                    f[i][j]=Math.max(f[i-1][j],f[i][j-1]-prices[i]);
//                if ( j%2==0 )
//                    f[i][j]=Math.max(f[i-1][j],f[i][j-1]+prices[i]);
//            }
//        }
//        return f[prices.length-1][num-1];
//    }
//}

//class Solution {
//    public int maxProfit(int[] prices, int fee) {
//        int[][] f=new int[prices.length][2];
//        f[0][0]=-prices[0];
//        for ( int i=1;i<prices.length;i++ ){
//            f[i][0]=Math.max(f[i-1][0],f[i-1][1]-prices[i]);
//            f[i][1]=Math.max(f[i-1][1],f[i-1][0]+prices[i]-fee);
//        }
//        return f[prices.length-1][1];
//    }
//}

//class Solution {
//    public int maxProfit(int[] prices) {
//        int[][] f=new int[prices.length][4];
//        //0表示买入股票的状态，1表示卖出股票（冷冻期前），2表示卖出股票（冷冻期后），3表示冷冻期时
//        f[0][0]=-prices[0];
//        for (int i=1;i<prices.length;i++ ){
//            f[i][0]=Math.max(f[i-1][0],Math.max(f[i-1][2]-prices[i],f[i-1][3]-prices[i]));
//            f[i][1]=f[i-1][0]+prices[i];
//            f[i][2]=Math.max(f[i-1][3],f[i-1][2]);
//            f[i][3]=f[i-1][1];
//        }
//        return Math.max(f[prices.length-1][1],Math.max(f[prices.length-1][2],f[prices.length-1][3]));
//    }
//}

//class Solution {
//    public int maxProfit(int[] prices) {
//        if ( prices.length==1 ){
//            return 0;
//        }
//        //先算出只买一个的所有情况，然后再在买一个的基础上再买一个
//        int[][] f=new int[prices.length][5];
//        f[0][1]=-prices[0];
//        f[0][3]=-prices[0];
//        //0列表示不进行任何操作
//        //1列表示第一次买入
//        //2表示第一次卖出
//        //3表示第二次买入
//        //4表示第二次卖出
//        //前面4列均是为了最后一列得出结果服务的，因为第n列需要第n-1列的数
//        for ( int i=1;i<prices.length;i++ ){
//            f[i][0]=f[i-1][0];
//            f[i][1]=Math.max(f[i-1][1],f[i-1][0]-prices[i]);
//            f[i][2]=Math.max(f[i-1][2],f[i-1][1]+prices[i]);
//            f[i][3]=Math.max(f[i-1][3],f[i-1][2]-prices[i]);
//            f[i][4]=Math.max(f[i-1][4],f[i-1][3]+prices[i]);
//        }
//        return f[prices.length-1][4];
////        int max=0;
////        int[][] f=new int[prices.length][2];
////        //f[0][0]=0;
////        for ( int i=1;i<prices.length;i++ ){
////            f[i][0]=maxProfitI(prices,i+1,0);
////        }
////        for ( int i=1;i<prices.length;i++ ){
////            f[i][1]=maxProfitI(prices,i+1,f[i][0]);
////            max=Math.max(max,f[i][1]);
////        }
////        return max;
//
//    }
//    public int maxProfitI(int[] prices,int end,int money) {
//        int[][] f=new int[end][2];
//        f[0][0]=money-prices[0];
//        f[0][1]=0;
//        for ( int i=1;i<end;i++ ){
//            f[i][0]=Math.max(f[i-1][0],-prices[i]);
//            f[i][1]=Math.max(f[i-1][0]+prices[i],f[i-1][1]);
//        }
//        return f[end-1][1];
//    }
//}

//class Solution {
//    public int maxProfit(int[] prices) {
//        int[][] f=new int[prices.length][2];
//        f[0][0]=-prices[0];
//        f[0][1]=0;
//        for ( int i=1;i<prices.length;i++ ){
//            f[i][0]=Math.max(f[i-1][0],f[i-1][1]-prices[i]);
//            f[i][1]=Math.max(f[i-1][1],f[i-1][0]+prices[i]);
//        }
//        return f[prices.length-1][1];
//    }
//}


//股票问题
//class Solution {
//    public int maxProfit(int[] prices) {
//        int[][] f=new int[prices.length][2];
//        f[0][0]=-prices[0];
//        f[0][1]=0;
//        for ( int i=1;i<prices.length;i++ ){
//            f[i][0]=Math.max(f[i-1][0],-prices[i]);
//            f[i][1]=Math.max(f[i-1][0]+prices[i],f[i-1][1]);
//        }
//        return f[prices.length-1][1];
//    }
//}

//class Solution {
//    public int rob(int[] nums) {
//        //加了一个限制条件，偷了第一个就不能偷最后一个
//        if ( nums.length<=2 ){
//            return 0;
//        }
//        if ( nums.length==3 ){
//            return nums[1];
//        }
//        //一个从0开始到倒数第二，一个从1开始到倒数第一
//
//        int res1=robIchange(nums,0,nums.length-1);
//        int res2=robIchange(nums,1,nums.length);
//        return res1>=res2?res1:res2;
//    }
//    private int robIchange(int[] nums,int statrt,int end) {
////        if ( nums.length==1 ){
////            return nums[0];
////        }
//        int max=0;
//        int[] f=new int[nums.length-1];
//        f[0]=nums[statrt];
//        f[1]=nums[statrt+1];
//        //需要一个从0到i-2的所有数的max
//        for ( int i=statrt+2;i<end;i++ ){
//            max=Math.max(max,f[i-2]);
//            if (statrt==0)
//                f[i]=nums[i]+max;
//            if (statrt==1)
//                f[i-1]=nums[i-1]+max;
//        }
//        //int max=Math.max(f[nums.length-2],f[nums.length-1]);
//        return f[nums.length-2]>=f[nums.length-3]?f[nums.length-2]:f[nums.length-3];
//    }
//}

//class Solution {
//    public int rob(int[] nums) {
//        if ( nums.length==1 ){
//            return nums[0];
//        }
//        int max=0;
//        int[] f=new int[nums.length];
//        f[0]=nums[0];
//        f[1]=nums[1];
//        //需要一个从0到i-2的所有数的max
//        for ( int i=2;i<nums.length;i++ ){
//            max=Math.max(max,f[i-2]);
//            f[i]=nums[i]+max;
//        }
//        //int max=Math.max(f[nums.length-2],f[nums.length-1]);
//        return f[nums.length-1]>=f[nums.length-2]?f[nums.length-1]:f[nums.length-2];
//    }
//}

//class Solution {
//    public boolean wordBreak(String s, List<String> wordDict) {
//        //完全背包问题
//        //String str=new String();
//        boolean[] f=new boolean[s.length()+1];
//        f[0]=true;
//        for ( int i=1;i<s.length()+1;i++ ){
//            for ( int j=0;j<wordDict.size();j++ ){
//                int len=wordDict.get(j).length();
//                if ( i>=len&&f[i-len] ){
//                    if ( s.substring(i-len,i).equals(wordDict.get(j)) ){
//                        f[i]=true;
//                        break;
//                    }
//                }
//            }
//        }
//        return f[s.length()];
//    }
//}

//class Solution {
//    public int numSquares(int n) {
//        int[] f=new int[n+1];
//        f[0]=0;
//        for ( int i=1;i<n+1;i++ ){
//            f[i]=n;
//        }
//        for ( int i=1;i<n+1;i++ ){
//            for ( int j=0;j<=i;j++ ){
//                if ( isSq(j) ){
//                        f[i]=Math.min(f[i],f[i-j]+1);
//                }
//            }
//        }
//        return f[n];
//    }
//    private boolean isSq(int n){
//        if (n<0){
//            return false;
//        }
//
//        double num=Math.sqrt(n);
//        if ( (int)num*(int)num==n ){
//            return true;
//        }else{
//            return false;
//        }
//    }
//}

//class Solution {
//    public int coinChange(int[] coins, int amount) {
//        //f为达到这个重量的最小的硬币数
//        int[] f=new int[amount+1];
//        f[0]=0;
//        for ( int i=0;i<amount+1;i++ ){
//            f[i]=Integer.MAX_VALUE;
//        }
//        for ( int i=0;i<amount+1;i++ ){
//            for ( int j=0;j<coins.length;j++ ){
//                if ( i>=coins[j] ){
//                    f[i]=Math.min(f[i],f[i-coins[j]]+1);
//                }
//            }
//        }
//        return f[amount];
//    }
//}


//class Solution {
//    public int combinationSum4(int[] nums, int target) {
//        int[] f=new int[target+1];
//        f[0]=1;
//        for ( int i=0;i<target+1;i++ ){
//            for ( int j=0;j<nums.length;j++ ){
//                if ( i>=nums[j] ){
//                    f[i]+=f[i-nums[j]];
//                }
//            }
//        }
//        return f[target];
//    }
//}

//class Solution {
//    public int change(int amount, int[] coins) {
//        //完全背包问题和01背包问题只是遍历顺序上的不同
//        //这一题中我让价值为方式的数量，重量为每个硬币的面值，背包容量为为amount总金额
//        //f就设为在某一个背包重量下他有的最多的组合方式
//        int[] f=new int[amount+1];
//        f[0]=1;
//        for ( int i=0;i<coins.length;i++ ){
//            for ( int j=coins[i];j<amount+1;j++ ){
//                f[j]+=f[j-coins[i]];
//            }
//        }
//        return f[amount];
//    }
//}

//class Solution {
//    public int findMaxForm(String[] strs, int m, int n) {
//        //写一个函数计算出一个字符串中包含的0和1的数量
//        //背包的容量是m个0和n个1，价值是字符串的个数
//        //int target=m+n+1;
//        int[][] f=new int[m+1][n+1];
//        f[0][0]=0;
//        for ( int i=0;i<strs.length;i++ ){
//            int num0=numStr(strs[i],"0");
//            int num1=numStr(strs[i],"1");
//            for ( int j=m;j>=num0;j-- ){
//                for ( int k=n;k>=num1;k-- ){
//                    f[j][k]=Math.max(f[j][k],f[j-num0][k-num1]+1);
//                }
//            }
//        }
//        return f[m][n];
//    }
//    private int numStr(String s,String str){
//        int cnt=0;
//        String[] ss=s.split("");
//        for ( int i=0;i<ss.length;i++ ){
//            if ( ss[i].equals(str) ){
//                cnt ++;
//            }
//        }
//        return cnt;
//    }
//}

//class Solution {
//    public int findTargetSumWays(int[] nums, int target) {
//        int sum=0;
//        for ( int i=0;i<nums.length;i++ ){
//            sum+=nums[i];
//        }
//        if ( (target+sum)%2==1 ){
//            return 0;
//        }
//        if ( target>sum ){
//            return 0;
//        }
//        int bagWeh=Math.abs((target+sum)/2);
//        int[] f=new int[bagWeh+1];
//        f[0]=1;
//        for ( int i=0;i<nums.length;i++ ){
//            for ( int j=bagWeh;j>=nums[i];j-- ){
//                f[j]+=f[j-nums[i]];
//            }
//        }
//        return f[bagWeh];
//    }
//}

//class Solution {
//    public int lastStoneWeightII(int[] stones) {
//        int sum=0;
//        for ( int i=0;i<stones.length;i++ ){
//            sum+=stones[i];
//        }
//        int target=sum/2;
//        int[] f=new int[target+1];
//        f[0]=0;
//
//        for ( int i=0;i<stones.length;i++ ){
//            for ( int j=target;j>=stones[i];j-- ){
//                f[j]=Math.max(f[j],f[j-stones[i]]+stones[i]);
//            }
//        }
//        return sum-f[target]-f[target];
//    }
//}


//class Solution {
//    public boolean canPartition(int[] nums) {
//        int sum=0;
//        for ( int i=0;i<nums.length;i++ ){
//            sum+=nums[i];
//        }
//        //得到了sum的值，即最大容量，现在可以用背包问题的解决方法进行解决
//        int[] f=new int[sum/2+1];
//        //设立一个初始条件
//        f[0]=0;
//        //进行一个升序排序方便计算
//        for ( int i=0;i<nums.length-1;i++ ){
//            for ( int j=0;j<nums.length-1-i;j++ ){
//                if ( nums[j+1]<nums[j] ){
//                    int temp=nums[j];
//                    nums[j]=nums[j+1];
//                    nums[j+1]=temp;
//                }
//            }
//        }
//        //开始进行动态规划
//        for ( int i=0;i<nums.length;i++ ){
//            for ( int j=sum/2;j>=nums[i];j-- ){
//                f[j]=Math.max(f[j],f[j-nums[i]]+nums[i]);
//            }
//        }
//        if ( f[sum/2]==sum/2 ){
//            return true;
//        }else{
//            return false;
//        }
//    }
//}
//开始背包问题、


//class Solution {
//    public int integerBreak(int n) {
//        //f[i]为当前i的拆分最大乘积
//        int[] f=new int[n];
//        f[0]=1;
//        for ( int i=1;i<n;i++ ){
//            f[i]=1;
//            for ( int j=1;j<i;j++ ){
//                f[i]=Math.max(f[i],Math.max(j*(i-j),j*f[i-j]));
//            }
//        }
//        return f[n-1];
//    }
//}

//class Solution {
//    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//        int m=obstacleGrid.length;
//        int n=obstacleGrid[0].length;
//        int[][] f=new int[m][n];
//        for ( int i=0;i<n;i++ ){
//            if ( obstacleGrid[0][i]!=1 ){
//                f[0][i]=1;
//            }else{
//                f[0][i]=0;
//            }
//        }
//        for ( int i=0;i<m;i++ ){
//            if ( obstacleGrid[i][0]!=1 ){
//                f[i][0]=1;
//            }else{
//                f[i][0]=0;
//            }
//        }
//
//        for ( int i=1;i<m;i++ ){
//            for ( int j=1;j<n;j++ ){
//                if ( obstacleGrid[i][j]!=1 ){
//                    f[i][j]=f[i-1][j]+f[i][j-1];
//                }
//            }
//        }
//        return f[m-1][n-1];
//    }
//}

//class Solution {
//    public int climbStairs(int n) {
//        int[] f=new int[n+1];
//        f[0]=1;
//        if ( n<1 ){
//            return 0;
//        }
//        f[1]=1;
//        for ( int i=2;i<n+1;i++ ){
//            f[i]=f[i-1]+f[i-2];
//        }
//        return f[n];
//    }
//}

//class Solution {
//    public int fib(int n) {
//        int[] f=new int[n];
//        f[0]=0;
//        f[1]=1;
//        for ( int i=2;i<n;i++ ){
//            f[i]=f[i-1]+f[i-2];
//        }
//        return f[n-1];
//    }
//}

//class Solution {
//    boolean res=false;
//    public boolean wordBreak(String s, List<String> wordDict) {
//        String path=new String();
//        breakTracking(s,wordDict,path,res);
//        return res;
//    }
//    private void breakTracking(String s,List<String> wordDict,String path,boolean res){
//        if ( path.equals(s)||res ){
//            res=true;
//            return;
//        }
//        if ( path.length()>=s.length() ){
//            return;
//        }
//        for ( int i=0;i<wordDict.size();i++ ){
//            String str=wordDict.get(i);
//            int num=str.length();
////            if ( s.substring(startIdx,num).equals(str) ){
////
////            }
//            int lenF=path.length();
//            path+=str;
//            breakTracking(s,wordDict,path,res);
//            //int lenB=path.length();
//            path=path.substring(0,lenF);
//        }
//        return;
//    }
//}

//class Solution {
//    //这题实在动态规划分类中找到的，但我认为用回溯会更好的解决
//    //用动态规划来求一些极值的问题会更加容易
//    public List<List<String>> partition(String s) {
//        List<String> path=new ArrayList<>();
//        List<List<String>> resList=new ArrayList<>();
//        String[] str=s.split("");
//        breakTracking(s,path,resList,1,0);
//        return resList;
//    }
//    private void breakTracking(String s,List<String> path,List<List<String>> resList,int num,int startIdx){
//        //每次都从第一个开始走，但第一次看一个，第二次回溯看两个，numidx就是存储看的数量
//        if ( num>=s.length() ){
//            List<String> list=new ArrayList<>();
//            list.addAll(path);
//            resList.add(list);
//            return;
//        }
//        for ( int i=startIdx;i<s.length();i++ ){
//            String str=s.substring(startIdx,num+startIdx);
//            if ( isPalin(str) ){
//                path.add(str);
//                int sizeF=path.size();
//                breakTracking(s,path,resList,num+i,startIdx+num);
//                //去除path的后几个元素
//                int sizeB=path.size();
//                if ( sizeB>sizeF ){//说明符合条件加上了，此时要去掉
//                    int n=sizeB-sizeF;
//                    path.remove(path.size()-1);
//                }
//            }else{
//                return;
//            }
//        }
//        return;
//    }
//    //用双指针法写一个判断是否是回文字符串的方法
//    private boolean isPalin(String s){
//        boolean isPal=true;
//        int front=0;
//        int back=s.length()-1;
//        String[] str=s.split("");
//        if ( s.length()==1 ){
//            return true;
//        }
//        while ( front<=back ){
//            if ( !str[front].equals(str[back]) ){
//                isPal=false;
//                break;
//            }
//            front ++;
//            back --;
//        }
//        return isPal;
//    }
//}

//class Solution {
//    public int maxProfit(int[] prices) {
//        int n=prices.length;
//        if ( n<=1 ){
//            return 0;
//        }
//        int min=prices[0];
//        int max=0;
//        //需要设置一个整形的f数组存储每个结果的答案
//        int[] f=new int[n];
//        f[0]=0;
//        for ( int i=1;i<n;i++ ){
//            //max=Math.max(max,prices[i]-min);
//            if ( min==prices[i-1]){
//                if ( prices[i]-prices[i-1]>=0 ){
//                    f[i]=prices[i]-prices[i-1];
//                }else{
//                    f[i]=0;
//                }
//            }else{
//                if ( prices[i]-prices[i-1]>=0 ){
//                    f[i]=f[i-1]+prices[i]-prices[i-1];
//                }else{
//                    f[i]=prices[i]-min>=0?prices[i]-min:0;
//                }
//
//            }
//            if ( f[i]>=max ){
//                max=f[i];
//            }
//            //f[i-1]=Math.max()
//            min=Math.min(min,prices[i]);
//        }
//        return max;
//    }
//}

//class Solution {
//    public int maxProfit(int[] prices) {
//        int n=prices.length;
//        if ( n<=1 ){
//            return 0;
//        }
//        //找到前面所有数的最小值
//        //让f存储以i为结尾的最大差值的数，迭代
//        int min=prices[0];
//        int max=0;
//        for ( int i=1;i<n;i++ ){
//            max=Math.max(max,prices[i]-min);
//            min=Math.min(min,prices[i]);
//        }
//        return max;
//    }
//}

//class Solution {//不对
//    public boolean isInterleave(String s1, String s2, String s3) {
//        int o=s3.length();
//        int m=s1.length();
//        int n=s2.length();
//        if ( m+n!=o ){
//            return false;
//        }
//        boolean[][] f=new boolean[m][n];
//        f[0][0]=true;
//        int s1Cnt=1;
//        int s2Cnt=1;
//        for ( int i=0;i<m+n;i++ ){
//            if ( s1.substring(s1Cnt-1,s1Cnt).equals(s3.substring(i,i+1)) ){
//                s1Cnt ++;
//            } else if ( s2.substring(s2Cnt-1,s2Cnt).equals(s3.substring(i,i+1)) ) {
//                s2Cnt ++;
//            }else{
//                return false;
//            }
//        }
//        return true;
//    }
//}


//class Solution {
//    public int numDecodings(String s) {
//        int n = s.length();
//        int[] f = new int[n + 1];
//        f[0] = 1;
//        for (int i = 1; i <= n; ++i) {
//            if (s.charAt(i - 1) != '0') {
//                f[i] += f[i - 1];
//            }
//            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
//                f[i] += f[i - 2];
//            }
//        }
//        return f[n];
//    }
//}

//class Solution {
//    public int numDecodings(String s) {
//        int n=s.length();
//        //以n为结尾的解码总数
//        int[] f=new int[n];
//        //g为以最后一个为结尾的总数
//        //int[] g=new int[n];
//        //h为以最后两个为结尾的总数
//        //int[] h=new int[n];
//        //f[0]=1;
//
//        String s0=s.substring(0,1);
//        if ( s0.equals("0")){
//            return 0;
//        }else{
//            f[0]=1;
//        }
//        if ( s.length()>1 ) {
//            int num = Integer.valueOf(s.substring(0, 2));
//            String s1=s.substring(1,2);
//            if ( s1.equals("0")||num>26 ) {
//                f[1] = 1;
//            } else {
//                f[1] = 2;
//            }
//        }
////        String s1=s.substring(1,2);
////        if (s1.equals("0")){
////            return
////        }
//        for ( int i=2;i<n;i++ ){
//            //判断是否有两种情况
//            String str2=s.substring(i-1,i+1);
//            int num2=Integer.valueOf(str2);
//            //String str1=s.substring(i,i+1);
//            //int num1=Integer.valueOf(str1);
//            String isZero=s.substring(i,i+1);
//            if ( isZero.equals("0") ){
//                f[i]=f[i-1]-f[i-2];
//            }else if( num2>26 ){
//                f[i]=f[i-1];
//            }else{
//                f[i]=f[i-1]+f[i-2];
//            }
//        }
//        return f[n-1];
//    }
//}
//class Solution {
//    List<String> res=new ArrayList<>();
//    public List<String> generateParenthesis(int n) {
//        //用递归方法写一个
//        //左括号的数量要时刻大于等于右括号，当右括号
//        if ( n<=0 ){
//            return res;
//        }
//        getParenthesis("",n,n);
//        return res;
//    }
//    public void getParenthesis( String str,int left,int right){
//        //终止条件
//        if ( left==0&&right==0 ){
//            //当left和right都为0的时候说明括号已经用完了，此时将完成的str加入这个线性表中
//            res.add(str);
//            return;
//        }
//        if ( left==right ){
//            getParenthesis(str+"(",left-1,right);
//        } else if ( left<right ){
//            if ( left>0 ){
//                getParenthesis(str+"(",left-1,right);
//            }
//            getParenthesis(str+")",left,right-1);
//        }
//    }
//}


//class Solution {
//    public List<String> generateParenthesis(int n) {
//        List f=new ArrayList();
//        f.add("()");
//        for ( int i=1;i<n;i++ ){
//            //int k=1;
//            int l=f.size();
//            int cnt;
//            int j=0;//需要遍历的次数
//            int k=0;//需要的位置
//            while ( j<l ){
//                cnt=0;
//                String str=f.get(k).toString();
//                f.remove(k);
//                //当（（（）））这种情况时，由于是对撑，所以有三种情况
//                //用双指针法进行判断，三重循环，时间复杂度很大
//                int front=0;
//                int back=str.length()-1;
//                int isHui=0;
//                String[] str0=str.split("");
//                while ( front<=back&&back!=1 ){
//                    if( str0[front].equals("(")&&str0[back].equals(")")){
//                        front ++;
//                        back --;
//                    }else{
//                        isHui=1;
//                    }
//                    if ( isHui==1 ){
//                        break;
//                    }
//                }
//                if ( isHui!=0||str.length()-1==1 ) {
//                    f.add(0, "(" + str + ")");
//                    f.add(0, "(" + ")" + str);
//                }else{
//                    f.add(0, "(" + str + ")");
//                    f.add(0, "(" + ")" + str);
//                    f.add(0,str + "(" + ")");
//                    cnt ++;
//                }
//                    //f.add(0,str+"("+")");
//                    cnt++;
//                    j++;
//                    k = k + 1 + cnt;
//
//            }
//            //k=l;
//        }
//        return f;
//    }
//}


//class Solution {
//    public String longestPalindrome(String s) {
//        String str="";
//        int max=0;
//        int n=s.length();
//        String f[]=new String[n];
//        f[0]=s.substring(0,1);
//        for ( int i=1;i<n;i++ ){
//            String str0=s.substring(0,i+1);
//            //将str转换成字符数组然后用双指针法判断是否回文
//            String str1[]=str0.split("");
//            int back=i;
//            for ( int j=0;j<i;j++ ){
//                int front=j;
//                int isHui=0;
//                //开始用双指针法判断是否回文
//                while ( front<=back ){
//                    if ( str1[front].equals(str1[back])){
//                        front ++;
//                        back --;
//                    }else{
//                        isHui=1;
//                        break;
//                    }
//                }
//                if ( isHui==0 ){
////    				System.out.println(j+" "+i);
//                    f[i]=s.substring(j,i+1);
//                    break;
//                }
//            }
//        }
//        for ( int i=0;i<n;i++ ){
//            if ( f[i]!=null ){
//                if ( f[i].length()>max ){
//                    max=f[i].length();
//                    str=f[i];
//                }
//            }
//        }
//        return str;
//    }
//}